public class ProductExceptSelf {
    // leetcode 除自身以外的数组的乘积
    // https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
    public int[] productExceptSelf(int[] nums) {
        // 前缀和知识
        int len = nums.length;
        int[] prev = new int[len], next = new int[len];
        prev[0] = 1;
        next[len-1] = 1;
        for (int i = 1; i < len; i++) {
            prev[i] = prev[i-1] * nums[i-1];
        }
        for (int i = len-2; i >= 0; i--) {
            next[i] = next[i+1] * nums[i+1];
        }
        int[] ret = new int[len];
        for (int i = 0; i < len; i++) {
            ret[i] = prev[i] * next[i];
        }
        return ret;
    }
}
